<?xml version='1.0' encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html lang="en" xml:lang="en" xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <link href="cpip.css" rel="stylesheet" type="text/css" />
    <title>File: /Users/paulross/dev/linux/linux-3.13/include/linux/rbtree.h</title>
  </head>
  <body>
    <h1>File: /Users/paulross/dev/linux/linux-3.13/include/linux/rbtree.h</h1>
    <p>Green shading in the line number column
means the source is part of the translation unit, red means it is conditionally excluded.
Highlighted line numbers link to the translation unit page. Highlighted macros link to
the macro page.</p>
    <pre><a name="1" /><span class="True">       1:</span> <span class="k">/*</span>
<a name="2" /><span class="True">       2:</span> <span class="k">  Red Black Trees</span>
<a name="3" /><span class="True">       3:</span> <span class="k">  (C) 1999  Andrea Arcangeli &lt;andrea@suse.de&gt;</span>
<a name="4" /><span class="True">       4:</span> <span class="k">  </span>
<a name="5" /><span class="True">       5:</span> <span class="k">  This program is free software; you can redistribute it and/or modify</span>
<a name="6" /><span class="True">       6:</span> <span class="k">  it under the terms of the GNU General Public License as published by</span>
<a name="7" /><span class="True">       7:</span> <span class="k">  the Free Software Foundation; either version 2 of the License, or</span>
<a name="8" /><span class="True">       8:</span> <span class="k">  (at your option) any later version.</span>
<a name="9" /><span class="True">       9:</span> <span class="k"></span>
<a name="10" /><span class="True">      10:</span> <span class="k">  This program is distributed in the hope that it will be useful,</span>
<a name="11" /><span class="True">      11:</span> <span class="k">  but WITHOUT ANY WARRANTY; without even the implied warranty of</span>
<a name="12" /><span class="True">      12:</span> <span class="k">  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the</span>
<a name="13" /><span class="True">      13:</span> <span class="k">  GNU General Public License for more details.</span>
<a name="14" /><span class="True">      14:</span> <span class="k"></span>
<a name="15" /><span class="True">      15:</span> <span class="k">  You should have received a copy of the GNU General Public License</span>
<a name="16" /><span class="True">      16:</span> <span class="k">  along with this program; if not, write to the Free Software</span>
<a name="17" /><span class="True">      17:</span> <span class="k">  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA</span>
<a name="18" /><span class="True">      18:</span> <span class="k"></span>
<a name="19" /><span class="True">      19:</span> <span class="k">  linux/include/linux/rbtree.h</span>
<a name="20" /><span class="True">      20:</span> <span class="k"></span>
<a name="21" /><span class="True">      21:</span> <span class="k">  To use rbtrees you&apos;ll have to implement your own insert and search cores.</span>
<a name="22" /><span class="True">      22:</span> <span class="k">  This will avoid us to use callbacks and to drop drammatically performances.</span>
<a name="23" /><span class="True">      23:</span> <span class="k">  I know it&apos;s not the cleaner way,  but in C (not in C++) to get</span>
<a name="24" /><span class="True">      24:</span> <span class="k">  performances and genericity...</span>
<a name="25" /><span class="True">      25:</span> <span class="k"></span>
<a name="26" /><span class="True">      26:</span> <span class="k">  See Documentation/rbtree.txt for documentation and samples.</span>
<a name="27" /><span class="True">      27:</span> <span class="k">*/</span>
<a name="28" /><span class="True">      28:</span> 
<a name="29" /><span class="Maybe">      29:</span> <span class="f">#</span><span class="n">ifndef</span>    <a href="cpu.c_macros_ref.html#_X0xJTlVYX1JCVFJFRV9IXzA_"><span class="b">_LINUX_RBTREE_H</span></a>
<a name="30" /><span class="Maybe">      30:</span> <span class="f">#</span><span class="n">define</span>    <a href="cpu.c_macros_ref.html#_X0xJTlVYX1JCVFJFRV9IXzA_"><span class="b">_LINUX_RBTREE_H</span></a>
<a name="31" /><span class="Maybe">      31:</span> 
<a name="32" /><span class="Maybe">      32:</span> <span class="f">#</span><span class="n">include</span> <span class="f">&lt;</span><span class="b">linux</span><span class="f">/</span><span class="b">kernel</span><span class="f">.</span><span class="b">h</span><span class="f">&gt;</span>
<a name="33" /><span class="Maybe">      33:</span> <span class="f">#</span><span class="n">include</span> <span class="f">&lt;</span><span class="b">linux</span><span class="f">/</span><span class="b">stddef</span><span class="f">.</span><span class="b">h</span><span class="f">&gt;</span>
<a name="34" /><span class="Maybe">      34:</span> 
<a name="35" /><span class="Maybe">      35:</span> <span class="m">struct</span> <span class="b">rb_node</span> <span class="f">{</span>
<a name="36" /><span class="Maybe">      36:</span>     <span class="m">unsigned</span> <span class="m">long</span>  <span class="b">__rb_parent_color</span><span class="f">;</span>
<a name="37" /><span class="Maybe">      37:</span>     <span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="b">rb_right</span><span class="f">;</span>
<a name="38" /><span class="Maybe">      38:</span>     <span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="b">rb_left</span><span class="f">;</span>
<a name="39" /><span class="Maybe">      39:</span> <span class="f">}</span> <span class="b">__attribute__</span><span class="f">(</span><span class="f">(</span><span class="b">aligned</span><span class="f">(</span><span class="m">sizeof</span><span class="f">(</span><span class="m">long</span><span class="f">)</span><span class="f">)</span><span class="f">)</span><span class="f">)</span><span class="f">;</span>
<a name="40" /><span class="Maybe">      40:</span>     <span class="k">/* The alignment might seem pointless, but allegedly CRIS needs it */</span>
<a name="41" /><span class="Maybe">      41:</span> 
<a name="42" /><span class="Maybe">      42:</span> <span class="m">struct</span> <span class="b">rb_root</span> <span class="f">{</span>
<a name="43" /><span class="Maybe">      43:</span>     <span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="b">rb_node</span><span class="f">;</span>
<a name="44" /><span class="Maybe">      44:</span> <span class="f">}</span><span class="f">;</span>
<a name="45" /><span class="Maybe">      45:</span> 
<a name="46" /><span class="Maybe">      46:</span> 
<a name="47" /><span class="Maybe">      47:</span> <span class="f">#</span><span class="n">define</span> <a href="cpu.c_macros_noref.html#_cmJfcGFyZW50XzA_"><span class="b">rb_parent</span></a><span class="f">(</span><span class="b">r</span><span class="f">)</span>   <span class="f">(</span><span class="f">(</span><span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="f">)</span><span class="f">(</span><span class="f">(</span><span class="b">r</span><span class="f">)</span><span class="f">-&gt;</span><span class="b">__rb_parent_color</span> <span class="f">&amp;</span> <span class="f">~</span><span class="c">3</span><span class="f">)</span><span class="f">)</span>
<a name="48" /><span class="Maybe">      48:</span> 
<a name="49" /><span class="Maybe">      49:</span> <span class="f">#</span><span class="n">define</span> <a href="cpu.c_macros_ref.html#_UkJfUk9PVF8w"><span class="b">RB_ROOT</span></a>    <span class="f">(</span><span class="m">struct</span> <span class="b">rb_root</span><span class="f">)</span> <span class="f">{</span> <a href="cpu.c_macros_ref.html#_TlVMTF8w"><span class="b">NULL</span></a><span class="f">,</span> <span class="f">}</span>
<a name="50" /><span class="Maybe">      50:</span> <span class="f">#</span><span class="n">define</span>    <a href="cpu.c_macros_noref.html#_cmJfZW50cnlfMA__"><span class="b">rb_entry</span></a><span class="f">(</span><span class="b">ptr</span><span class="f">,</span> <span class="b">type</span><span class="f">,</span> <span class="b">member</span><span class="f">)</span> <a href="cpu.c_macros_ref.html#_Y29udGFpbmVyX29mXzA_"><span class="b">container_of</span></a><span class="f">(</span><span class="b">ptr</span><span class="f">,</span> <span class="b">type</span><span class="f">,</span> <span class="b">member</span><span class="f">)</span>
<a name="51" /><span class="Maybe">      51:</span> 
<a name="52" /><span class="Maybe">      52:</span> <span class="f">#</span><span class="n">define</span> <a href="cpu.c_macros_ref.html#_UkJfRU1QVFlfUk9PVF8w"><span class="b">RB_EMPTY_ROOT</span></a><span class="f">(</span><span class="b">root</span><span class="f">)</span>  <span class="f">(</span><span class="f">(</span><span class="b">root</span><span class="f">)</span><span class="f">-&gt;</span><span class="b">rb_node</span> <span class="f">==</span> <a href="cpu.c_macros_ref.html#_TlVMTF8w"><span class="b">NULL</span></a><span class="f">)</span>
<a name="53" /><span class="Maybe">      53:</span> 
<a name="54" /><span class="Maybe">      54:</span> <span class="k">/* &apos;empty&apos; nodes are nodes that are known not to be inserted in an rbree */</span>
<a name="55" /><span class="Maybe">      55:</span> <span class="f">#</span><span class="n">define</span> <a href="cpu.c_macros_noref.html#_UkJfRU1QVFlfTk9ERV8w"><span class="b">RB_EMPTY_NODE</span></a><span class="f">(</span><span class="b">node</span><span class="f">)</span>  \
<a name="56" /><span class="Maybe">      56:</span>     <span class="f">(</span><span class="f">(</span><span class="b">node</span><span class="f">)</span><span class="f">-&gt;</span><span class="b">__rb_parent_color</span> <span class="f">==</span> <span class="f">(</span><span class="m">unsigned</span> <span class="m">long</span><span class="f">)</span><span class="f">(</span><span class="b">node</span><span class="f">)</span><span class="f">)</span>
<a name="57" /><span class="Maybe">      57:</span> <span class="f">#</span><span class="n">define</span> <a href="cpu.c_macros_ref.html#_UkJfQ0xFQVJfTk9ERV8w"><span class="b">RB_CLEAR_NODE</span></a><span class="f">(</span><span class="b">node</span><span class="f">)</span>  \
<a name="58" /><span class="Maybe">      58:</span>     <span class="f">(</span><span class="f">(</span><span class="b">node</span><span class="f">)</span><span class="f">-&gt;</span><span class="b">__rb_parent_color</span> <span class="f">=</span> <span class="f">(</span><span class="m">unsigned</span> <span class="m">long</span><span class="f">)</span><span class="f">(</span><span class="b">node</span><span class="f">)</span><span class="f">)</span>
<a name="59" /><span class="Maybe">      59:</span> 
<a name="60" /><span class="Maybe">      60:</span> 
<a name="61" /><span class="Maybe">      61:</span> <span class="m">extern</span> <span class="m">void</span> <span class="b">rb_insert_color</span><span class="f">(</span><span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="f">,</span> <span class="m">struct</span> <span class="b">rb_root</span> <span class="f">*</span><span class="f">)</span><span class="f">;</span>
<a name="62" /><span class="Maybe">      62:</span> <span class="m">extern</span> <span class="m">void</span> <span class="b">rb_erase</span><span class="f">(</span><span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="f">,</span> <span class="m">struct</span> <span class="b">rb_root</span> <span class="f">*</span><span class="f">)</span><span class="f">;</span>
<a name="63" /><span class="Maybe">      63:</span> 
<a name="64" /><span class="Maybe">      64:</span> 
<a name="65" /><span class="Maybe">      65:</span> <span class="k">/* Find logical next and previous nodes in a tree */</span>
<a name="66" /><span class="Maybe">      66:</span> <span class="m">extern</span> <span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="b">rb_next</span><span class="f">(</span><span class="m">const</span> <span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="f">)</span><span class="f">;</span>
<a name="67" /><span class="Maybe">      67:</span> <span class="m">extern</span> <span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="b">rb_prev</span><span class="f">(</span><span class="m">const</span> <span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="f">)</span><span class="f">;</span>
<a name="68" /><span class="Maybe">      68:</span> <span class="m">extern</span> <span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="b">rb_first</span><span class="f">(</span><span class="m">const</span> <span class="m">struct</span> <span class="b">rb_root</span> <span class="f">*</span><span class="f">)</span><span class="f">;</span>
<a name="69" /><span class="Maybe">      69:</span> <span class="m">extern</span> <span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="b">rb_last</span><span class="f">(</span><span class="m">const</span> <span class="m">struct</span> <span class="b">rb_root</span> <span class="f">*</span><span class="f">)</span><span class="f">;</span>
<a name="70" /><span class="Maybe">      70:</span> 
<a name="71" /><span class="Maybe">      71:</span> <span class="k">/* Postorder iteration - always visit the parent after its children */</span>
<a name="72" /><span class="Maybe">      72:</span> <span class="m">extern</span> <span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="b">rb_first_postorder</span><span class="f">(</span><span class="m">const</span> <span class="m">struct</span> <span class="b">rb_root</span> <span class="f">*</span><span class="f">)</span><span class="f">;</span>
<a name="73" /><span class="Maybe">      73:</span> <span class="m">extern</span> <span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="b">rb_next_postorder</span><span class="f">(</span><span class="m">const</span> <span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="f">)</span><span class="f">;</span>
<a name="74" /><span class="Maybe">      74:</span> 
<a name="75" /><span class="Maybe">      75:</span> <span class="k">/* Fast replacement of a single node without remove/rebalance/add/rebalance */</span>
<a name="76" /><span class="Maybe">      76:</span> <span class="m">extern</span> <span class="m">void</span> <span class="b">rb_replace_node</span><span class="f">(</span><span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="b">victim</span><span class="f">,</span> <span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="m">new</span><span class="f">,</span> 
<a name="77" /><span class="Maybe">      77:</span>                 <span class="m">struct</span> <span class="b">rb_root</span> <span class="f">*</span><span class="b">root</span><span class="f">)</span><span class="f">;</span>
<a name="78" /><span class="Maybe">      78:</span> 
<a name="79" /><span class="Maybe">      79:</span> <span class="m">static</span> <span class="m">inline</span> <span class="m">void</span> <span class="b">rb_link_node</span><span class="f">(</span><span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span> <span class="b">node</span><span class="f">,</span> <span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span> <span class="b">parent</span><span class="f">,</span>
<a name="80" /><span class="Maybe">      80:</span>                 <span class="m">struct</span> <span class="b">rb_node</span> <span class="f">*</span><span class="f">*</span> <span class="b">rb_link</span><span class="f">)</span>
<a name="81" /><span class="Maybe">      81:</span> <span class="f">{</span>
<a name="82" /><span class="Maybe">      82:</span>     <span class="b">node</span><span class="f">-&gt;</span><span class="b">__rb_parent_color</span> <span class="f">=</span> <span class="f">(</span><span class="m">unsigned</span> <span class="m">long</span><span class="f">)</span><span class="b">parent</span><span class="f">;</span>
<a name="83" /><span class="Maybe">      83:</span>     <span class="b">node</span><span class="f">-&gt;</span><span class="b">rb_left</span> <span class="f">=</span> <span class="b">node</span><span class="f">-&gt;</span><span class="b">rb_right</span> <span class="f">=</span> <a href="cpu.c_macros_ref.html#_TlVMTF8w"><span class="b">NULL</span></a><span class="f">;</span>
<a name="84" /><span class="Maybe">      84:</span> 
<a name="85" /><span class="Maybe">      85:</span>     <span class="f">*</span><span class="b">rb_link</span> <span class="f">=</span> <span class="b">node</span><span class="f">;</span>
<a name="86" /><span class="Maybe">      86:</span> <span class="f">}</span>
<a name="87" /><span class="Maybe">      87:</span> 
<a name="88" /><span class="Maybe">      88:</span> <span class="f">#</span><span class="n">define</span> <a href="cpu.c_macros_noref.html#_cmJfZW50cnlfc2FmZV8w"><span class="b">rb_entry_safe</span></a><span class="f">(</span><span class="b">ptr</span><span class="f">,</span> <span class="b">type</span><span class="f">,</span> <span class="b">member</span><span class="f">)</span> \
<a name="89" /><span class="Maybe">      89:</span>     <span class="f">(</span><span class="f">{</span> <span class="b">typeof</span><span class="f">(</span><span class="b">ptr</span><span class="f">)</span> <span class="b">____ptr</span> <span class="f">=</span> <span class="f">(</span><span class="b">ptr</span><span class="f">)</span><span class="f">;</span> \
<a name="90" /><span class="Maybe">      90:</span>        <span class="b">____ptr</span> <span class="f">?</span> <a href="cpu.c_macros_noref.html#_cmJfZW50cnlfMA__"><span class="b">rb_entry</span></a><span class="f">(</span><span class="b">____ptr</span><span class="f">,</span> <span class="b">type</span><span class="f">,</span> <span class="b">member</span><span class="f">)</span> <span class="f">:</span> <a href="cpu.c_macros_ref.html#_TlVMTF8w"><span class="b">NULL</span></a><span class="f">;</span> \
<a name="91" /><span class="Maybe">      91:</span>     <span class="f">}</span><span class="f">)</span>
<a name="92" /><span class="Maybe">      92:</span> 
<a name="93" /><span class="Maybe">      93:</span> <span class="k">/**</span>
<a name="94" /><span class="Maybe">      94:</span> <span class="k"> * rbtree_postorder_for_each_entry_safe - iterate over rb_root in post order of</span>
<a name="95" /><span class="Maybe">      95:</span> <span class="k"> * given type safe against removal of rb_node entry</span>
<a name="96" /><span class="Maybe">      96:</span> <span class="k"> *</span>
<a name="97" /><span class="Maybe">      97:</span> <span class="k"> * @pos:    the &apos;type *&apos; to use as a loop cursor.</span>
<a name="98" /><span class="Maybe">      98:</span> <span class="k"> * @n:        another &apos;type *&apos; to use as temporary storage</span>
<a name="99" /><span class="Maybe">      99:</span> <span class="k"> * @root:    &apos;rb_root *&apos; of the rbtree.</span>
<a name="100" /><span class="Maybe">     100:</span> <span class="k"> * @field:    the name of the rb_node field within &apos;type&apos;.</span>
<a name="101" /><span class="Maybe">     101:</span> <span class="k"> */</span>
<a name="102" /><span class="Maybe">     102:</span> <span class="f">#</span><span class="n">define</span> <a href="cpu.c_macros_noref.html#_cmJ0cmVlX3Bvc3RvcmRlcl9mb3JfZWFjaF9lbnRyeV9zYWZlXzA_"><span class="b">rbtree_postorder_for_each_entry_safe</span></a><span class="f">(</span><span class="b">pos</span><span class="f">,</span> <span class="b">n</span><span class="f">,</span> <span class="b">root</span><span class="f">,</span> <span class="b">field</span><span class="f">)</span> \
<a name="103" /><span class="Maybe">     103:</span>     <span class="m">for</span> <span class="f">(</span><span class="b">pos</span> <span class="f">=</span> <a href="cpu.c_macros_noref.html#_cmJfZW50cnlfc2FmZV8w"><span class="b">rb_entry_safe</span></a><span class="f">(</span><span class="b">rb_first_postorder</span><span class="f">(</span><span class="b">root</span><span class="f">)</span><span class="f">,</span> <span class="b">typeof</span><span class="f">(</span><span class="f">*</span><span class="b">pos</span><span class="f">)</span><span class="f">,</span> <span class="b">field</span><span class="f">)</span><span class="f">;</span> \
<a name="104" /><span class="Maybe">     104:</span>          <span class="b">pos</span> <span class="f">&amp;&amp;</span> <span class="f">(</span><span class="f">{</span> <span class="b">n</span> <span class="f">=</span> <a href="cpu.c_macros_noref.html#_cmJfZW50cnlfc2FmZV8w"><span class="b">rb_entry_safe</span></a><span class="f">(</span><span class="b">rb_next_postorder</span><span class="f">(</span><span class="f">&amp;</span><span class="b">pos</span><span class="f">-&gt;</span><span class="b">field</span><span class="f">)</span><span class="f">,</span> \
<a name="105" /><span class="Maybe">     105:</span>             <span class="b">typeof</span><span class="f">(</span><span class="f">*</span><span class="b">pos</span><span class="f">)</span><span class="f">,</span> <span class="b">field</span><span class="f">)</span><span class="f">;</span> <span class="c">1</span><span class="f">;</span> <span class="f">}</span><span class="f">)</span><span class="f">;</span> \
<a name="106" /><span class="Maybe">     106:</span>          <span class="b">pos</span> <span class="f">=</span> <span class="b">n</span><span class="f">)</span>
<a name="107" /><span class="Maybe">     107:</span> 
<a name="108" /><span class="True">     108:</span> <span class="f">#</span><span class="n">endif</span>    <span class="k">/* _LINUX_RBTREE_H */</span>
<a name="109" /><span class="True">     109:</span> </pre>
  </body>
</html>
